package 剑指offer;


/*
 * Author：江松
 * Date：2023/3/19 13:24
 *
 滑动窗口的最大值：
 暴力法：遍历区间，遍历窗口

 单调队列：
 1，如果后一个元素大于前面的元素，那么前面元素就没有存在的意义了(删除队尾)
 2，判断队头元素是否过期(删除队头)
 3,为了好判断过期，队列里存放下标
 */

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;

public class Main43 {
    public ArrayList<Integer> maxInWindows(int [] num, int size) {
        int len=num.length;
        ArrayList<Integer>ans=new ArrayList<>();
        if(size==0||size>len)return ans;
        Deque<Integer>deque=new LinkedList<>();
        for(int i=0;i<len;++i){
            //维持单调性
            while(!deque.isEmpty()&&num[i]>num[deque.peekLast()]){
                deque.pollLast();
            }
            deque.offerLast(i);
            System.out.println(deque.peekFirst());
            //判断过期
            if(deque.peekFirst()+size>=i){
                deque.pollFirst();
            }
            if(i>=size-1)ans.add(num[deque.peekFirst()]);
        }
        return ans;
    }
    /*
    //暴力法
    public ArrayList<Integer> maxInWindows(int [] num, int size) {
        int len=num.length;
        ArrayList<Integer> ans=new ArrayList<>();
        //遍历左窗口位置
        for(int i=0;i<len-size+1;++i){
            int mx=num[i];
            //遍历窗口内找最大值
            for(int j=i+1;j<i+size;++j){
                if(mx<num[j]){
                    mx=num[j];
                }
            }
            ans.add(mx);
        }
        return ans;
    }
    */
}
